/*
 * GClubDistributor.java
 * Created on 22 août 2009
 *
 * VirtualHockey Internet Platform
 * http://code.google.com/p/virtualhockey/
 *
 * Copyright (c) 2005-2009, Jens and Jan Janke (VirtualHockey Project)
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program. If not, see http://www.gnu.org/licenses/.
 */

package com.hockeo.vhbase.seasoncycle.services;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;

import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;

import com.hockeo.vhbase.data.dao.IGDao;
import com.hockeo.vhbase.data.dao.club.GClub;

/**
 * Utility class that helps distributing clubs into different groups. It can e.g. be used
 * to distribute clubs onto matches or groups in international contests. It uses a random
 * generator but provides several configuration possibilities that influence the drawing.
 * It is e.g. possible to avoid that teams of the same national association are grouped
 * together (if possible).
 *
 * This class is not thread-safe! Please use one instance of it for each running thread if
 * you require multiple threads to use it.
 *
 * @version $Id$
 * @author jjanke
 */
public final class GClubDistributor
{
  private static Log              d_logger = LogFactory.getLog( GClubDistributor.class );
  private static GClubDistributor d_instance;
  private final IGDao             d_dao;
  private final Random            d_random;

  /**
   * Initializes the club distributor creator.
   *
   * @param dao the DAO to use for all database interactions.
   */
  private GClubDistributor( final IGDao dao )
  {
    d_dao = dao;
    d_random = new Random();
  }

  /**
   * Returns the singleton instance.
   *
   * @param dao the DAO to use for all database interactions.
   */
  public static GClubDistributor get( final IGDao dao )
  {
    if ( d_instance == null )
      d_instance = new GClubDistributor( dao );

    return d_instance;
  }

  /**
   * Distributes the clubs given as input into the specified number of bundles. Each
   * created bundle will have the same size.
   *
   * @param listInput list of clubs to distribute (they are expected to be in seeding
   *          order - the best seeded first and the worst seeded last)
   * @param nNumBundles the number of bundles (groups or matches) to create
   * @param fAvoidSameNationality indicates whether it is allowed that two clubs from the
   *          same national association are grouped together in one bundle
   * @param fUseSeedLists if seed lists should be used for the creation of bundles
   * @return a list of bundles (each bundle is itself a list and contains all the clubs
   *         that have been added to it)
   */
  public List<List<GClub>> distributeClubs( List<GClub> listInput, int nNumBundles, boolean fAvoidSameNationality,
      boolean fUseSeedLists )
  {
    if ( listInput == null || listInput.size() % nNumBundles != 0 )
      throw new IllegalArgumentException( "The input list is either null or the number of contained clubs is "
          + "not dividable without rest by the number of bundles to be created." );

    final int nBundleSize = listInput.size() / nNumBundles;
    final List<List<GClub>> listResult = new ArrayList<List<GClub>>();
    final List<List<GClub>> listSeedHats = new ArrayList<List<GClub>>();
    final Map<String, List<GClub>> mapByNationality = new HashMap<String, List<GClub>>();
    int nMaxTeamsSameNationality = 1;

    fillSeedHats( listInput, listSeedHats, nBundleSize, !fUseSeedLists );

    if ( fAvoidSameNationality )
    {
      nMaxTeamsSameNationality = fillNationalityMap( listInput, mapByNationality );

      // if it is impossible to ensure that teams from the same assoc meet, switch off the
      // nationality check by setting the variable nMaxTeamsSameNationality to 1
      //
      if ( nMaxTeamsSameNationality > nNumBundles )
      {
        d_logger.warn( "There are " + nMaxTeamsSameNationality + " from the same nationality although only "
            + nNumBundles + " should be created. It is impossible to avoid that two teams from the same "
            + "national association will be added to the same bundle." );

        nMaxTeamsSameNationality = 1;
      }
    }

    // create the result bundles
    //
    for ( int i = 0; i < nNumBundles; i++ )
      listResult.add( new ArrayList<GClub>() );

    // execute the actual drawing (at first distribute all teams from the 1st seed hat,
    // then from the 2nd, etc.)
    //
    for ( List<GClub> listHat : listSeedHats )
    {
      // create a list with the indexes of all the bundles that have not yet received a
      // team from the current hat
      //
      List<Integer> listBundlesWithoutTeamFromHat = new ArrayList<Integer>();

      for ( int i = 0; i < nNumBundles; i++ )
        listBundlesWithoutTeamFromHat.add( Integer.valueOf( i ) );

      // distribute all teams from the hat until it is empty
      //
      while ( !listHat.isEmpty() )
      {
        // draw a team from the hat and (remove it in the same time from the hat)
        //
        GClub club = listHat.remove( d_random.nextInt( listHat.size() ) );

        // now determine the bundle into which to add the team
        //
        int iBundle = listBundlesWithoutTeamFromHat.remove( d_random.nextInt( listBundlesWithoutTeamFromHat.size() ) ).intValue();

        // check if the club can be placed in the determined bundle if nationality
        // constraint checking is enabled
        //
        if ( nMaxTeamsSameNationality > 1 )
          iBundle = checkNationalityDistribution( club, iBundle, listResult, mapByNationality,
              listBundlesWithoutTeamFromHat );

        // put the club into the determined bundle and remove bundle index from list of
        // bundles that have not yet received a team from the current hat
        //
        listResult.get( iBundle ).add( club );
      }
    }

    return listResult;
  }

  /**
   * Checks if the given club can be added to the bundle with the given index. It is only
   * possible to add it when no other club having the same nationality as the club to add
   * is already part of the list. If the bundle already contains a list it is at first
   * check if it is possible to add the club to one of the bundles that have not yet
   * received a team from the current hat. If this is not possible neither, the other
   * bundles are also checked with the goal to place the club in one of the other bundles
   * putting the club from the other bundle into the bundle with the given index instead.
   *
   * @param club the club to be added to a bundle
   * @param iBundle the index of the bundle into which to add the club
   * @param listResult the list of all bundles
   * @param mapByNationality the map that contains all clubs by their nationality
   * @param listBundlesWithoutTeamFromHat list of indexes from all bundles that have not
   *          yet received a team from the current hat
   */
  private int checkNationalityDistribution( GClub club, int iBundle, List<List<GClub>> listResult,
      Map<String, List<GClub>> mapByNationality, List<Integer> listBundlesWithoutTeamFromHat )
  {
    String strAssocId = club.getAssociation().getId();

    // If there is anyway only one team from the given association, there is nothing to do
    // here
    //
    if ( mapByNationality.get( strAssocId ).size() <= 1 )
      return iBundle;

    // Check all teams from the chosen hat
    //
    boolean fOtherClubSameAssoc = false;
    for ( GClub clubBundle : listResult.get( iBundle ) )
      if ( clubBundle.getAssociation().getId().equals( strAssocId ) )
      {
        fOtherClubSameAssoc = true;
        break;
      }

    // if there is no other club from the same assoc, everything is ok
    //
    if ( !fOtherClubSameAssoc )
      return iBundle;

    // now, let's look if any of the bundles that have not yet received a team from this
    // hat can receive this club
    //
    for ( Integer iOtherBundle : listBundlesWithoutTeamFromHat )
    {
      fOtherClubSameAssoc = false;
      for ( GClub clubBundle : listResult.get( iOtherBundle.intValue() ) )
        if ( clubBundle.getAssociation().getId().equals( strAssocId ) )
        {
          fOtherClubSameAssoc = true;
          break;
        }

      // if we have found a matching bundle, let's put back the original bundle index into
      // the list of bundles that did not yet receive a team from the current hat and
      // return instead the id of the newly determined bundle
      //
      if ( !fOtherClubSameAssoc )
      {
        listBundlesWithoutTeamFromHat.add( Integer.valueOf( iBundle ) );
        listBundlesWithoutTeamFromHat.remove( iOtherBundle );
        return iOtherBundle.intValue();
      }
    }

    // if we arrive here, it is impossible to add the team to any of the bundles not
    // having received a team from the current hat. We now have to check all other
    // bundles.
    //
    for ( int iOtherBundle = 0; iOtherBundle < listResult.size(); iOtherBundle++ )
    {
      // we have already checked the original destination bundle and all the bundles not
      // yet having received a team from the current hat
      //
      if ( iOtherBundle == iBundle || listBundlesWithoutTeamFromHat.contains( Integer.valueOf( iOtherBundle ) ) )
        continue;

      // check if the bundle contains a club with the same nationality, if yes continue
      //
      for ( GClub clubOtherBundle : listResult.get( iOtherBundle ) )
        if ( clubOtherBundle.getAssociation().getId().equals( strAssocId ) )
          continue;

      // the current bundle contains only clubs with a different nationality we must find
      // out if one of the clubs from the determined bundle can be placed into the
      // originally foreseen bundle. If yes, we can swap the clubs and everything is
      // right.
      //
      fOtherClubSameAssoc = false;
      GClub clubToSwap = null;
      for ( GClub clubOtherBundle : listResult.get( iOtherBundle ) )
      {
        for ( GClub clubOriginalBundle : listResult.get( iBundle ) )
          if ( clubOtherBundle.getAssociation().equals( clubOriginalBundle.getAssociation() ) )
          {
            fOtherClubSameAssoc = true;
            break;
          }

        if ( !fOtherClubSameAssoc )
        {
          clubToSwap = clubOtherBundle;
          break;
        }
      }

      if ( clubToSwap != null )
      {
        listResult.get( iOtherBundle ).remove( clubToSwap );
        listResult.get( iBundle ).add( clubToSwap );
        return iOtherBundle;
      }
    }

    // Normally we should not arrive here. If yes, it means that we weren't able to find
    // any bundle into which to place the club. In this case just add it to the originally
    // foreseen bundle.
    //
    return iBundle;
  }

  /**
   * Iterates over the input list and distributes the clubs according to their national
   * association appartenance.
   *
   * @param listInput the club input list
   * @param mapByNationality the map in which each association id is mapped to the number
   *          of clubs
   * @return the maximum number of clubs for an association
   */
  private int fillNationalityMap( List<GClub> listInput, Map<String, List<GClub>> mapByNationality )
  {
    int cMax = 0;

    for ( GClub club : listInput )
    {
      String strAssocId = club.getAssociation().getId();
      List<GClub> listClubsPerAssoc = mapByNationality.get( strAssocId );

      if ( listClubsPerAssoc == null )
      {
        listClubsPerAssoc = new ArrayList<GClub>();
        mapByNationality.put( strAssocId, listClubsPerAssoc );
      }

      listClubsPerAssoc.add( club );
      if ( listClubsPerAssoc.size() > cMax )
        cMax = listClubsPerAssoc.size();
    }

    return cMax;
  }

  /**
   * Creates the hats that are later used for the actual draw of the matches.
   *
   * @param listInput the input list containing all the clubs to be put into the different
   *          hats
   * @param listSeedHats the list of hats
   * @param nNumHats the number of hats to be filled
   * @param fRandom whether to distribute the clubs randomly or not, if <code>false</code>
   *          the input list is supposed to contain the clubs in seeding order
   */
  private void fillSeedHats( List<GClub> listInput, List<List<GClub>> listSeedHats, int nNumHats, boolean fRandom )
  {
    final int nHatSize = listInput.size() / nNumHats;

    for ( int iHat = 0; iHat < nNumHats; iHat++ )
    {
      List<GClub> listHat = new ArrayList<GClub>();

      for ( int iClub = 0; iClub < nHatSize; iClub++ )
        if ( fRandom )
        {
          int n = d_random.nextInt( listInput.size() );

          listHat.add( listInput.get( n ) );
          listInput.remove( n );
        }
        else
          listHat.add( listInput.get( iHat * nHatSize + iClub ) );

      listSeedHats.add( listHat );
    }
  }

}
